

/**
 * @ClassName TopologicalSort
 * @Description 拓扑排序
 * @Author ZJX
 * @Date 2024/10/26 17:28
 * @Version 1.0
 */

//   适用于有向无环图  拓扑排序顺序可能不止一种   拓扑排序也可以判断有没有环
//   这种排序方式在很多场景中有应用，比如任务调度、编译依赖等。
package graph;
import java.util.*;

public class TopologicalSortKahn {

    public static List<Integer> topologicalSort(int numNodes, List<List<Integer>> adjList) {
        int[] inDegree = new int[numNodes];
        for (List<Integer> edges : adjList) {
            for (int node : edges) {
                inDegree[node]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numNodes; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            topoOrder.add(node);

            for (int neighbor : adjList.get(node)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        if (topoOrder.size() != numNodes) {
            throw new IllegalArgumentException("Graph contains a cycle");
        }

        return topoOrder;
    }

    public static void main(String[] args) {
        int numNodes = 6;
        List<List<Integer>> adjList = Arrays.asList(
                Arrays.asList(2, 3),   // 节点0指向2, 3
                Arrays.asList(3, 4),   // 节点1指向3, 4
                Arrays.asList(),       // 节点2无出边
                Arrays.asList(5),      // 节点3指向5
                Arrays.asList(5),      // 节点4指向5
                Arrays.asList()        // 节点5无出边
        );

        List<Integer> topoOrder = topologicalSort(numNodes, adjList);
        System.out.println("拓扑排序结果: " + topoOrder);
    }
}

